home *** CD-ROM | disk | FTP | other *** search
/ Aminet 3 / Aminet 3 - July 1994.iso / Aminet / util / misc / aterminfo.lha / comp_hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-12  |  2.0 KB  |  102 lines
  1.  
  2. /* This work is copyrighted. See COPYRIGHT.OLD & COPYRIGHT.NEW for   *
  3. *  details. If they are missing then this copy is in violation of    *
  4. *  the copyright conditions.                                        */
  5.  
  6. /*
  7.  *    comp_hash.c --- Routines to deal with the hashtable of capability
  8.  *            names.
  9.  *
  10.  */
  11.  
  12. #include <string.h>
  13. #include "compiler.h"
  14. #include "term.h"
  15.  
  16. /*
  17.  *    make_hash_table()
  18.  *
  19.  *    Takes the entries in cap_table[] and hashes them into cap_hash_table[]
  20.  *    by name.  There are Captabsize entries in cap_table[] and Hashtabsize
  21.  *    slots in cap_hash_table[].
  22.  *
  23.  */
  24.  
  25. void make_hash_table()
  26. {
  27.     int    i;
  28.     int    hashvalue;
  29.     int    collisions = 0;
  30.     static  int hash_function();
  31.  
  32.     for (i=0; i < Captabsize; i++)
  33.     {
  34.         hashvalue = hash_function(cap_table[i].nte_name);
  35.         DEBUG(9, "%d\n", hashvalue);
  36.  
  37.         if (cap_hash_table[hashvalue] != (struct name_table_entry *) 0)
  38.         collisions++;
  39.  
  40.         cap_table[i].nte_link = cap_hash_table[hashvalue];
  41.         cap_hash_table[hashvalue] = &cap_table[i];
  42.     }
  43.  
  44.     DEBUG(3, "Hash table complete\n%d collisions ", collisions);
  45.     DEBUG(3, "out of %d entries\n", Captabsize);
  46. }
  47.  
  48.  
  49. /*
  50.  *    int hash_function(string)
  51.  *
  52.  *    Computes the hashing function on the given string.
  53.  *
  54.  *    The current hash function is the sum of each consectutive pair
  55.  *    of characters, taken as two-byte integers, mod Hashtabsize.
  56.  *
  57.  */
  58.  
  59. static
  60. int
  61. hash_function(string)
  62. char    *string;
  63. {
  64.     long    sum = 0;
  65.  
  66.     while (*string)
  67.     {
  68.         sum += *string + (*(string + 1) << 8);
  69.         string++;
  70.     }
  71.  
  72.     return (sum % Hashtabsize);
  73. }
  74.  
  75.  
  76. /*
  77.  *    struct name_table_entry *
  78.  *    find_entry(string)
  79.  *
  80.  *    Finds the entry for the given string in the hash table if present.
  81.  *    Returns a pointer to the entry in the table or 0 if not found.
  82.  *
  83.  */
  84.  
  85. struct name_table_entry *
  86. find_entry(string)
  87. char    *string;
  88. {
  89.     int    hashvalue;
  90.     struct name_table_entry    *ptr;
  91.  
  92.     hashvalue = hash_function(string);
  93.  
  94.     ptr = cap_hash_table[hashvalue];
  95.  
  96.     while (ptr != (struct name_table_entry *) 0  &&
  97.                       strcmp(ptr->nte_name, string) != 0)
  98.         ptr = ptr->nte_link;
  99.  
  100.     return (ptr);
  101. }
  102.